// 2025/3/20
// https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked
// 单词搜索

class Solution {
    public:
        bool dfs(vector<vector<char>>& board, string& word, int pos, int i, int j)
        {
            if(pos == word.size() - 1) return true;
            char tmp = board[i][j];
            board[i][j] = '\0';
            if(i > 0 && board[i - 1][j] == word[pos + 1] && dfs(board, word, pos + 1, i - 1, j))
                return true;
            if(i < board.size() - 1 && board[i + 1][j] == word[pos + 1] && dfs(board, word, pos + 1, i + 1, j))
                return true;
            if(j > 0 && board[i][j - 1] == word[pos + 1] && dfs(board, word, pos + 1, i, j - 1))
                return true;
            if(j < board[i].size() - 1 && board[i][j + 1] == word[pos + 1] && dfs(board, word, pos + 1, i, j + 1))
                return true;
    
            board[i][j] = tmp;
            return false;
        }
    
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size(), n = board[0].size();
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(board[i][j] == word[0] && dfs(board, word, 0, i, j))
                        return true;
                }
            }
            return false;
        }
    };